/*
提交链接:https://leetcode.cn/problems/count-special-integers/
2376. 统计特殊整数
赖德檀 2024/10/5
*/

class Solution {
public:
int f(vector<int>& cnt,int n,int len,int k,int start)
{
    if(len==0) return 1;
    int ans=0;
    int sum = (n/k)%10;
    for(int i=0;i<sum;i++)
    {
        if((start&(1<<i))==0)
        ans+=cnt[len-1];   //确定了高位len的值,那么len-1的值就随便匹配了
    }
    if((start &(1<<sum))==0)
    ans += f(cnt,n,len-1,k/10,start|(1<<sum));
    return ans;
}

    int countSpecialNumbers(int n) {
        int len = 1;
        int t = n/10;
        int k = 1;
        int start=0;
        int ans=0;
        while(t>0)
        {
            t/=10;
            len++;
            k*=10;
        }
        vector<int>cnt(len,0);
        cnt[0]=1;
        for(int i=1,k=10-len+1;i<len;k++,i++)
        {
            cnt[i]=cnt[i-1]*k;
        }
        if(len>=2)
        {
            ans=9;
            for(int i=2,a=9,b=9;i<len;b--,i++) 
            {
                a*=b;
                ans+=a;
            } 
        }
        int sum = n/k;
        ans += (sum-1) * cnt[len-1];
        ans += f(cnt,n,len-1,k/10,start|(1<<sum));
        return ans;
    }
};